package com.lun.medium;

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class CountGoodNodesInBinaryTree {
	
	//方法一：递归版
    public int goodNodes(TreeNode root) {
		return goodNodes(root, Integer.MIN_VALUE);
    }
    
    public int goodNodes(TreeNode node, int max) {
    	if(node == null) return 0;
    	int nextMax = Math.max(max, node.val);
    	return (node.val >= max ? 1 : 0) + goodNodes(node.left, nextMax)// 
    			+ goodNodes(node.right, nextMax);
    }
    
    //方法二：迭代版
    public int goodNodes2(TreeNode root) {
    	if(root == null)
    		return 0;
    	
    	int result = 0;
    	
    	LinkedList<Object[]> stack = new LinkedList<>(); 
    	stack.add(new Object[] {root, Integer.MIN_VALUE});
    	while(!stack.isEmpty()) {
    		Object[] arr = stack.pop();
    		TreeNode node = (TreeNode)arr[0];
    		int max = (int)arr[1];
    		
    		if(node.val >= max)
    			result++;
    		
    		int nextMax = Math.max(max, node.val);
    		if(node.right != null)
    			stack.push(new Object[] {node.right, nextMax});
    		
    		if(node.left != null)
    			stack.push(new Object[] {node.left, nextMax});
    	}
    	
    	return result;
    }
    
    
}
